package com.zql.JianZhiOffer;

import java.util.*;

/**
 * Created By ShuHua on 2022/4/26.
 */
public class Offer_03 {
    public static void main(String[] args) {
        String s= "342001";
        System.out.println(s.substring(1,6));

        int repeatNumber2 = findRepeatNumber4(new int[]{3, 4, 2, 2, 0, 1});
        System.out.println(repeatNumber2);
    }

    /**
     * 利用map
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();

        int result =0;
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                result= nums[i];
                break;
            }else {
                map.put(nums[i],1);
            }
        }
        return result;
    }

    /**
     * 利用数组转String的方案
     * 不行 因为如果有1 和11 则不满足
     * @param nums
     * @return
     */
    public static int findRepeatNumber2(int[] nums) {
        int result = -1;
        String string = "";
        for(int i=0;i<nums.length;i++) string+=String.valueOf(nums[i]);
        for(int i=0;i<nums.length;i++){
            if(i==0){
                if(string.substring(1,nums.length).contains(String.valueOf(nums[i]))){
                    result = nums[0];
                    break;
                }
            } else  {
                if(string.substring(0,i).contains(String.valueOf(nums[i]))||string.substring(i+1,nums.length).contains(String.valueOf(nums[i]))){
                    result=nums[i];
                    break;
                }

            }
        }
        return result;
    }

    /**
     * 利用set集合的特性
     * @param nums
     * @return
     */
    public int findRepeatNumber3(int[] nums) {
        Set<Integer> map = new HashSet<>();

        int result =0;
        for(int i=0;i<nums.length;i++){
            if(!map.add(nums[i])) {
                result=nums[i];
                break;
            }
        }
        return result;
    }

    /**
     * 原地置换法
     * 一个长度为 n 的数组里的所有数字都在 0～n-1 的范围内
     * 索引和值是一对多的关系，可以通过遍历数组，让值和索引一一对应；即 num[i]=i
     * 当num[i]!=i 把索引为和索引为num[i]的值交换
     *  num[i]=i i++;
     *  当num[i]!=i && nums[nums[i]] = num[i] 则为重复数字
     * @param nums
     * @return
     */
    public static int findRepeatNumber4(int[] nums) {
        int res=-1;
        int i=0;
        while(i<nums.length){
            if(nums[i]==i){
                i++;
            }else if(nums[i]!=i){
                if(nums[nums[i]]==nums[i]){
                    res=nums[i];
                    break;
                }
                int tmp = nums[nums[i]];
                nums[nums[i]] =nums[i];
                nums[i]=tmp;
            }
        }
        return res;
    }

    /**
     * 原地置换 优化版 少了两层判断
     * @param nums
     * @return
     */
    public static int findRepeatNumber5(int[] nums) {
        int i=0;
        while(i<nums.length){
            if(nums[i]==i){
                i++;
                continue;
            }
            if(nums[nums[i]]==nums[i]){
                return nums[i];
            }
            int tmp = nums[nums[i]];
            nums[nums[i]] =nums[i];
            nums[i]=tmp;

        }
        return -1;
    }


}
